package com.tiny.work.leetcode;

import org.junit.Test;

public class searchRange {


    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};

        if (nums.length <= 0) {
            return result;
        }
        searchRange(nums, target, 0, nums.length - 1, result);
        return result;
    }

    private void searchRange(int[] nums, int target, int l, int r, int[] result) {

        if ((r == nums.length - 1 && nums[r] == target)
            || (r < nums.length - 1 && nums[r] == target && nums[r + 1] != target)) {
            result[1] = r;
        }
        if ((l == 0 && nums[l] == target)
            || (l > 0 && nums[l] == target && nums[l - 1] != target)) {
            result[0] = l;
        }
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        if (nums[mid] < target) {
            searchRange(nums, target, mid + 1, r, result);
        } else if (nums[mid] > target) {
            searchRange(nums, target, l, mid, result);
        } else if (nums[mid] == target) {
            searchRange(nums, target, l, mid, result);
            searchRange(nums, target, mid + 1, r, result);
        }
    }

    @Test
    public void tsr() {
        int[] nums;
        nums = new int[]{1, 2, 3, 8, 8, 23};
        int[] result = searchRange(nums, 8);
        assert result[0] == 3;
        assert result[1] == 4;
        nums = new int[]{2, 3, 8, 8, 8, 23};
        result = searchRange(nums, 8);
        assert result[0] == 2;
        assert result[1] == 4;
        nums = new int[]{2, 3, 8, 8, 8, 8, 23};
        result = searchRange(nums, 8);
        assert result[0] == 2;
        assert result[1] == 5;
        nums = new int[]{2, 3, 8, 8, 8, 8, 8, 23};
        result = searchRange(nums, 8);
        assert result[0] == 2;
        assert result[1] == 6;
        nums = new int[]{};
        result = searchRange(nums, 8);
        assert result[0] == -1;
        assert result[1] == -1;
        nums = new int[]{1};
        result = searchRange(nums, 1);
        assert result[0] == 0;
        assert result[1] == 0;
        nums = new int[]{1};
        result = searchRange(nums, 8);
        assert result[0] == -1;
        assert result[1] == -1;
        nums = new int[]{5, 7, 7, 8, 8, 10};
        result = searchRange(nums, 81);
        assert result[0] == -1;
        assert result[1] == -1;
    }
}
